<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <!-- 你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1:

输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释: 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意:

给定的列表可能包含重复元素，所以在这里升序表示 >= 。
1 <= k <= 3500
-105 <= 元素的值 <= 105
对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -->
    <script>
        const smallestRange = (nums) => {
            let sort_arr = []
            let nums_length = nums.length
            for (let n_i = 0; n_i < nums_length; n_i++) {
                let s_nums = nums[n_i]
                let s_length = s_nums.length
                for (let s_i=0; s_i < s_length; s_i++) {
                    sort_arr.push({
                        nums: s_nums[s_i],
                        father_num: n_i
                    })
                }
            }
            sort_arr = sort_arr.sort((a, b) => {
                return a.nums - b.nums
            })
            console.log('sort2',sort_arr)
            const s_len = sort_arr.length
            let count = 0, l_i = 0, hash_map = {}, minLen = Infinity, minStart = 0;
            for (let r_i = 0; r_i < s_len; r_i++) {
                const s_item = sort_arr[r_i] // 排序好的单项
                if (!hash_map[s_item.father_num] || hash_map[s_item.father_num] === 0) {
                    count++
                    hash_map[s_item.father_num] = 0
                }
                hash_map[s_item.father_num] += 1
                while (count === nums_length && l_i <= r_i) {
                    const right_value = s_item.nums
                    const left_value = sort_arr[l_i].nums
                    const father_num = sort_arr[l_i].father_num
                    if (right_value - left_value < minLen) {
                        minLen = right_value - left_value
                        minStart = left_value
                    }
                    hash_map[father_num] -= 1
                    if (hash_map[father_num] === 0) count--
                    l_i+=1
                }
            }
            console.log('hash_map',hash_map)
            return [minStart, minStart + minLen]
        }
    </script>
</body>

</html>